#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>


typedef struct _Trie {
	bool terminal;
	struct _Trie *next[26];
} Trie;


void
lowercase(char *word, unsigned int word_len)
{
	for (int x = 0; x < word_len; x += 1) {
		if (isupper(word[x])) {
			word[x] = tolower(word[x]);
		}
	}
}


/*
   Malloc a new part of the trie
*/
Trie *
new_trie()
{
	Trie *fresh_trie = (Trie *)malloc(sizeof(Trie));
	assert(fresh_trie);

	for (int x = 0; x <26; x += 1) {
		fresh_trie->next[x] = NULL;
	}

	fresh_trie->terminal = false;

	return fresh_trie;
}

/*
   Calculate an int index based on an ASCII letter (upper or lowercase)
*/
int
char_index(char letter)
{
	assert(isalpha(letter));

	if (isupper(letter)) {
		letter = tolower(letter);
	}

	return ((int)letter) - 97;
}

/*
   Construct a trie from /usr/share/dict/words
*/
Trie *
build_trie(FILE *dict_FILE)
{
	assert(dict_FILE);

	Trie *dict_trie = new_trie();

	char word_buffer[1000]; // Assume no word longer than 1000

	while (!feof(dict_FILE)) {
		fscanf(dict_FILE, "%s\n", word_buffer);
		char *cur_char = word_buffer;
		Trie *cur_trie = dict_trie;

		while (*cur_char != '\0') {
			if (cur_trie->next[char_index(*cur_char)]) {
				cur_trie =
					cur_trie->next[char_index(*cur_char)];
			}
			else {
				Trie *fresh_trie = new_trie();

				cur_trie->next[char_index(*cur_char)] =
					fresh_trie;
				cur_trie = fresh_trie;
			}

			cur_char++;
		}

		cur_trie->terminal = true;
	}

	return dict_trie;
}

/*
   Verify a word can be found in the trie
*/
bool
check(char *word_start, unsigned int word_len, Trie *dict_trie)
{
	Trie *cur_trie = dict_trie;
	char lowercased_word[word_len+1];

	lowercase(lowercased_word, word_len);

	while (*word_start != '\0') {
		if (!(cur_trie = cur_trie->next[char_index(*word_start)])) {
			return false;
		}
		word_start++;
	}

	if (!cur_trie->terminal) {
		return false;
	}

	return true;
}


int
main(int argc, char* argv[])
{
	assert(argc == 3);

	FILE *dict_FILE = fopen(argv[1], "r");
	Trie *dict_trie = build_trie(dict_FILE);

	char *word_start = argv[2];
	unsigned int word_len = 0;
	char cur_char;

	do {
		cur_char = *(word_start + word_len);
		if ((cur_char == ' ') || (cur_char == '\0')) {
			char word_buffer[word_len+1];

			strncpy(word_buffer, word_start, word_len);
			word_buffer[word_len] = '\0';

			if (!check(word_buffer, word_len, dict_trie)) {
				printf("%s\n", word_buffer);
			}

			word_start = word_start + word_len + 1;
			word_len = 0;
			while (*word_start == ' ') {
				word_start += 1;
			}
			continue;
		}
		word_len += 1;
	} while (cur_char != '\0');

	return EXIT_SUCCESS;
}
